#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
typedef struct BiTnode
{
    BiTnode *lchild,*rchild;
    int data;
}BiTnode,*tree;
tree create(string s,int n){
    if(n==0) return 0;
    tree root=(tree)malloc(sizeof(struct BiTnode));
    tree p=root;
    stack<tree> nodeStack;
    int i=0;
    while(p||!nodeStack.empty()){
        if(p!=NULL){//一直创建p的左右孩子，直到p为空
            if(s[i]==0){
                p->data=i;
                p->lchild=NULL;
                p->rchild=NULL;
            }
            else if(s[i]==1){
                tree node=(tree)malloc(sizeof(struct BiTnode));
                p->data=i;
                p->lchild=node;
                p->rchild=NULL;
            }
            else{
                tree node1=(tree)malloc(sizeof(struct BiTnode));
                tree node2=(tree)malloc(sizeof(struct BiTnode));
                p->data=i;
                p->lchild=node1;
                p->rchild=node2;
            }
            nodeStack.push(p);//入栈并访问左孩子
            p=p->lchild;
            i++;
        }else{//当前p为空，说明其根节点已经被访问过，现在构建右子树
            p=nodeStack.top();
            nodeStack.pop();
            p=p->rchild;
        }
    }
    return root;
}
void preOrder_Iterative(tree root){//根 左 右
    if(root==NULL)  
        return;
    stack<tree> s;
    s.push(root);
    while(!s.empty()){
        tree p=s.top();
        printf("%d ",p->data);
        s.pop();
        if(p->rchild) s.push(p->rchild);
        if(p->lchild) s.push(p->lchild);
    }
}
void inOrder_Iterative(tree root){
    if(root==NULL)  
        return;
    stack<tree> s;
    tree curNode;
    curNode=root;
    while(curNode||!s.empty()){
        while(curNode){//找到最左节点
            s.push(curNode);
            curNode=curNode->lchild;
        }//此时栈顶没有左子树，或者左子树已经访问完
        curNode=s.top();
        printf("%d ",curNode->data);
        s.pop();
        curNode=curNode->rchild;
    }
}
void postOrder_Iterative(tree root){//左 右 根
    if(root==NULL)  
        return;
    stack<tree> s;
    stack<tree> res;
    s.push(root);
    while(!s.empty()){
        tree node=s.top();
        res.push(node);
        s.pop();
        if(node->lchild) s.push(p->lchild);
        if(node->rchild) s.push(p->rchild);
    }
    while(!res.empty()){
        printf("%d ",res.top()->data);
        res.pop();
    }
}
int main(){
    string str="21200110";
    create(str,strlen(str)-1);
    return 0;
}